package com.tgy.algorithm.base._递归;

public class _N皇后问题 {

    public static int queen(int n) {
        
        if (n <= 3) {
            return 0;
        }
        
        int[] loc = new int[n];
        return doQueen(0,loc);
    }
    
    public static int doQueen(int index,int[] loc) {
        int len = loc.length;
        if (index >= len) {
            // 是一种可行方案
            return 1;
        }
        int result = 0;
        for (int i = 0; i < len; i++) {
            //当前选择的位置坐标: [index,i]
            loc[index] = i;
            if (index > 0) {
                boolean isValid = true;
                for (int j = 0; j < index; j++) {
                    // 之前选中的位置 [j,loc[j]]
                    // 判断列是否相同，以及是否在同一个对角线上，因为协律45度
                    if ((loc[j] == i) || (Math.abs(index - j) == Math.abs(i - loc[j]))) {
                        isValid = false;
                        break;
                    }
                }
                if (isValid) {
                    result += doQueen(index+1,loc);
                }
            }else {
                result += doQueen(index+1,loc);
            }
        }
        
        return result;
    }


    public static void main(String[] args) {
        int queen = queen(8);
        System.out.println(queen);
    }
}
